package  main.java.leetcode.editor.cn;
//2023-07-27 14:28:26
//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 6667 👎 0

class LongestPalindromicSubstring {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new LongestPalindromicSubstring().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2){
            return s;
        }

        boolean[][] dp = new boolean[len][len];
        //所有长度为1的子串都是回文串
        for(int i = 0;i<len;i++){
            dp[i][i] = true;
        }

        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();

        for(int left = 2;left<=len;left++){
            //枚举左边界
            for(int i = 0;i<len;i++){
                int right = left+i-1;
                //右越界越界，直接结束
                if(right>=len){
                    break;
                }
                if(charArray[i] != charArray[right]){
                    dp[i][right] = false;
                }else {
                    if (right-i < 3) {
                        dp[i][right] = true;
                    }else {
                        dp[i][right] = dp[i+1][right-1];
                    }
                }
                //只要dp[i][left] == true，则表示子串 s[i---left]是回文，此时记录回文长度的起始位置
                if(dp[i][right] && right-i+1 > maxLen){
                    maxLen = right - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
